/*

Archivo: "globals.h"

Implementación de las clases base abstractas,
para un contenedor, un nodo y uniterador.

Autor: Diego Luna

Primera versión: 5-6-2012

*/


#ifndef __BASES_H_INCLUDED
#define __BASES_H_INCLUDED

#include <cstdlib>
#include <typeinfo>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

#include "globals.h"


// Tipo de iterador, permite decidir el iterador realmente implementado.
enum Iterator_Type {DEFAULT_ITERATOR = 0, SECOND_ITERATOR = 1, THIRD_ITERATOR = 2, FOURTH_ITERATOR = 3};

// Tipo de elemento "extremo".
enum Special_Node {SN_BEGIN, SN_R_BEGIN, SN_END, SN_R_END};

// Dirección de avance del iterador bidireccional (solo cambia el sentido de los operadores de incremento y decremento).
enum Iterator_Direction {ID_FORWARD = 0, ID_BACKWARD = 1};

// Forward declarations.
template <typename T, Iterator_Type itt>
class Base_Iterator;

template<typename T>
class Base_Container;

#define STR_CLASS_NAME "class "

/* ========================= SetImplementation - Begin ========================== */
// Clase abstracta base para la implementación de los contenedores usados por
// el conjunto. La clase es abastracta y solo define una interfaz.

template <typename T>
class SetImplementation
{

public:

    // Tipos definidos en forma standard para un "container" compatible con la STL.
    typedef T valueTpe;
    typedef valueTpe& reference;
    typedef const valueTpe& const_reference;
    typedef Base_Iterator<T, DEFAULT_ITERATOR> iterator;
    //typedef const Base_Iterator<T, DEFAULT_ITERATOR> const_iterator;
    typedef int differenceTpe;
    typedef size_t sizeTpe;


    // ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

    SetImplementation();

    virtual ~SetImplementation();

    // ++++++++++++++++++++++++ Constructores\Destructores - End +++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Métodos públicos - Begin +++++++++++++++++++++++++++++++++++++++

    // Devuelve el iterador al primer elemento.
    virtual iterator begin() const = 0;

    // Devuelve el iterador al siguiente al último elemento.
    virtual iterator end() const = 0;

    // Devuelve el iterador al anterior al primer elemento.
    virtual iterator rend() const = 0;

    // Devuelve el iterador al último elemento.
    virtual iterator rbegin() const = 0;

    // Agrega un elemento al contenedor.
    virtual bool add(const T&, bool = false) = 0;

    // Agrega un elemento al contenedor y devuelve un iterador al mismo,
    // o al elemento existente en caso de existir previamente.
    virtual iterator add_or_get(const T&) = 0;

    // Elimina un elemento del contenedor (si se encuentra).
    virtual bool remove(const T&) = 0;

    // Determina si un elemento se encuentra en el contenedor.
    virtual bool includes(const T&) const = 0;

    // Vacía el contenedor.
    virtual void wipe() = 0;

    // Determina si el contenedor esta vacío.
    virtual bool is_empty() const = 0;

    // Devuelve la cantidad de elementos en el contenedor.
    virtual size_t size() const = 0;

    // Imprime los elementos contenidos.
    virtual void print(std::ostream&) const = 0;

    // Devuelve un string que identifica a la clase del contenedor.
    virtual std::string class_ID() const = 0;

    // ++++++++++++++++++++++++ Métodos públicos - End ++++++++++++++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Operadores - Begin ++++++++++++++++++++++++++++++++++++++++++++++

    // Operador de asignación.
    virtual SetImplementation<T>& operator=(const SetImplementation<T>&);

    // Operador de salida.
    std::ostream& operator<<(std::ostream &);

    // ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++++++++


};
/* ========================= SetImplementation - Begin ========================== */


/* ========================= Base_Node - Begin ========================== */
template <typename T>
class Base_Node
{

public:

    //************************
    // Atributos de Base_Node.

    // Clave.
    T key_;

    //************************


    // ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

    // Constructor.
    Base_Node(const Base_Container<T>&);

    // Constructor.
    Base_Node(const Base_Container<T>&, const T&);

    // Constructor copia.
    Base_Node(const Base_Node<T>&);

    // Destructor.
    virtual ~Base_Node();

    // ++++++++++++++++++++++++ Constructores\Destructores - End +++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Métodos públicos - Begin +++++++++++++++++++++++++++++++++++++++

    // Devuelve una referencia al contenedor.
    const Base_Container<T>& container();

    // ++++++++++++++++++++++++ Métodos públicos - End ++++++++++++++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Operadores - Begin +++++++++++++++++++++++++++++++++++++++++++++

    // Operador de asignación.
    Base_Node<T>& operator=(const Base_Node<T>&);

    // ++++++++++++++++++++++++ Operadores - End +++++++++++++++++++++++++++++++++++++++++++++++

private:

    // ++++++++++++++++++++++++ Métodos privados - Begin ++++++++++++++++++++++++++++++++++++++++

    // Contenedor.
    const Base_Container<T>* container_;

    // ++++++++++++++++++++++++ Métodos privados - End ++++++++++++++++++++++++++++++++++++++++++

};
/* ========================= Base_Node - End ========================== */


/* ========================= Base_Container - Begin ========================== */
// Implementa la lógica básica de un contenedor en base a un grupo de métodos
// virtuales puros que los contenedores derivados implementan.

template<typename T>
class Base_Container: public SetImplementation<T>
{

public:

    // Tipos definidos en forma standard para un "container" compatible con la STL.
    typedef T valueTpe;
    typedef typename SetImplementation<T>::reference reference;
    typedef typename SetImplementation<T>::const_reference const_reference;
    typedef typename SetImplementation<T>::iterator iterator;
    //typedef typename SetImplementation<T>::const_iterator const_iterator;
    typedef typename SetImplementation<T>::differenceTpe differenceTpe;
    typedef typename SetImplementation<T>::sizeTpe sizeTpe;


    // ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

    // Constructor.
    Base_Container();

    // Constructor copia.
    Base_Container(const Base_Container<T>&);

    // Destructor.
    virtual ~Base_Container();

    // ++++++++++++++++++++++++ Constructores\Destructores - End +++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Métodos públicos - Begin +++++++++++++++++++++++++++++++++++++++

    // Devuelve el iterador al primer elemento.
    virtual iterator begin() const;

    // Devuelve el iterador al siguiente al último elemento.
    virtual iterator end() const;

    // Devuelve el iterador al anterior al primer elemento.
    virtual iterator rend() const;

    // Devuelve el iterador al último elemento.
    virtual iterator rbegin() const;

    // Agrega un elemento al contenedor.
    virtual bool add(const T&, bool = false);

    // Agrega un elemento al contenedor y devuelve un iterador al mismo, o al elemento existente
    // en caso de existir previamente.
    virtual iterator add_or_get(const T&);

    // Elimina un elemento del contenedor (si se encuentra).
    virtual bool remove(const T&);

    // Determina si un elemento se encuentra en el contenedor.
    virtual bool includes(const T&) const;

    // Vacía el contenedor.
    virtual void wipe();

    // Determina si el contenedor esta vacío.
    virtual bool is_empty() const;

    // Devuelve la cantidad de elementos en el contenedor.
    virtual size_t size() const;

    // Imprime los elementos contenidos.
    virtual void print(std::ostream&) const;

    // Devuelve un string que identifica a la clase del contenedor.
    virtual std::string class_ID() const;

    // ++++++++++++++++++++++++ Métodos públicos - End ++++++++++++++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Operadores - Begin ++++++++++++++++++++++++++++++++++++++++++++++

    // Operador de asignación.
    virtual Base_Container<T>& operator=(const Base_Container<T>&);

    // ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++++++++


    // El iterador tiene acceso a la representación interna del contenedor.
    template <typename, Iterator_Type>
    friend class Base_Iterator;

protected:

    // ++++++++++++++++++++++++ Métodos protegidos - Begin +++++++++++++++++++++++++++++++++++++++

    // Agrega un elemento al contenedor (Devuelve puntero al nodo).
    Base_Node<T>* add_hidden(const T&, bool = false);
	
    // Devuelve un puntero al elemento con la clave indicada, devuelve NULL en caso de no encontrarse.
    virtual Base_Node<T>* find_node(const T&) const = 0;

    // Agrega un elemento al contenedor devolviendo un puntero al elemento insertado o NULL si no se insertó.
    virtual Base_Node<T>* add_node(const T&, bool) = 0;

    // Elimina un elemento del contenedor.
	// Este método es llamado primero, en
	// caso de devolver "false" se llama al
	// que toma un nodo por parámetro.
    virtual bool delete_node_by_key(const T&, bool&) = 0;

    // Elimina un elemento del contenedor.
    virtual void delete_node(Base_Node<T>*) = 0;

    // Elimina todos los elementos del contenedor.
    virtual void delete_nodes() = 0;

    // Devuelve el sucesor de un elemento.
    virtual Base_Node<T>* next(Base_Node<T>*, Iterator_Type) const = 0;

    // Devuelve el predecesor de un elemento.
    virtual Base_Node<T>* previous(Base_Node<T>*, Iterator_Type) const = 0;

    // Devuelve el primer elemento para un tipo de iterador.
    virtual Base_Node<T>* first(Iterator_Type) const = 0;

    // Devuelve el último elemento para un tipo de iterador.
    virtual Base_Node<T>* last(Iterator_Type) const = 0;

    // ++++++++++++++++++++++++ Métodos protegidos - End ++++++++++++++++++++++++++++++++++++++++++

private:

    //************************
    // Atributos de Base_Container.

    // Cantidad de elementos.
    size_t node_count_;

    //************************

};
/* ========================= Base_Container - End ========================== */


/* ========================= Base_Iterator - Begin ========================== */

// La clase base usada "std::iterator", es una clase que solo define una serie de
// typedef anidados que compatibilizan el iterador con los algoritmos de la STL,
// se podrían haber declarado esos typedef y no derivar de esta clase, pero de esta
// manera queda mas clara la intención de implementar un iterador compatible con la STL.
template <typename T, Iterator_Type itt>
class Base_Iterator: public std::iterator<std::bidirectional_iterator_tag, T>
{

public:

    // ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

    // Constructor.
    Base_Iterator(const Base_Container<T>&);

    // Constructor copia.
    Base_Iterator(const Base_Iterator&);

    // Constructor que crea e inicializa el elemento en algún extremo o más allá.
    Base_Iterator(const Base_Container<T>&, Special_Node);

    // Destructor.
    virtual ~Base_Iterator();

    // ++++++++++++++++++++++++ Constructores\Destructores - End +++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Métodos públicos - Begin +++++++++++++++++++++++++++++++++++++++

    // Devuelve la dirección de avance del iterador bidireccional
    // (solo cambia el sentido de los operadores de incremento y decremento).
    Iterator_Direction get_direction();

    // Setea la dirección de avance del iterador bidireccional
    // (solo cambia el sentido de los operadores de incremento y decremento).
    void set_direction(Iterator_Direction);

    // Fuerza el iterador al primer elemento.
    void goto_begin();

    // Fuerza el iterador al elemento siguiente al último.
    void goto_end();

    // Fuerza el iterador al elemento anterior al primero.
    void goto_rend();

    // Fuerza el iterador al último elemento.
    void goto_rbegin();

    // ++++++++++++++++++++++++ Métodos públicos - End ++++++++++++++++++++++++++++++++++++++++++


    // ++++++++++++++++++++++++ Operadores - Begin +++++++++++++++++++++++++++++++++++++++++++++

    // Operador de desreferenciación.
    virtual const T& operator*();

    // Operador de comparación por igualdad.
    bool operator==(const Base_Iterator<T, itt>&) const;

    // Operador de comparación por desigualdad.
    bool operator!=(const Base_Iterator<T, itt>&) const;

    // Operador de asignación.
    Base_Iterator<T, itt>& operator=(const Base_Iterator<T, itt>&);

    // Operador de pre-incremento.
    Base_Iterator<T, itt>& operator++();

    // Operador de pre-decremento.
    Base_Iterator<T, itt>& operator--();

    // Operador de post-incremento.
    Base_Iterator<T, itt> operator++(int);

    // Operador de post-decremento.
    Base_Iterator<T, itt> operator--(int);

    // ++++++++++++++++++++++++ Operadores - End ++++++++++++++++++++++++++++++++++++++++++++++++

    // El contenedor tiene acceso al iterador.
    friend class Base_Container<T>;

protected:

    // ++++++++++++++++++++++++ Constructores\Destructores - Begin +++++++++++++++++++++++++++++

    // Constructor protegido que crea el iterador e inicializa el elemento a uno en particular.
    Base_Iterator(const Base_Container<T>&, Base_Node<T>*);

    // ++++++++++++++++++++++++ Constructores\Destructores - End +++++++++++++++++++++++++++++++

    //************************
    // Atributos de Base_Container.

    // Contenedor.
    const Base_Container<T>* container_;

    //************************

    // ++++++++++++++++++++++++ Métodos protegidos - Begin +++++++++++++++++++++++++++++++++++++++

    // Incrementa el iterador.
    void next();

    // Decrementa el iterador.
    void previous();

    // ++++++++++++++++++++++++ Métodos protegidos - End ++++++++++++++++++++++++++++++++++++++++++

private:

    // ++++++++++++++++++++++++ Métodos privados - Begin ++++++++++++++++++++++++++++++++++++++++++

    // Fuerza el iterador a un extremo determinado.
    void set_node(Special_Node);

    // Fuerza el iterador a un elemento determinado.
    void set_node(Base_Node<T>*);

    // ++++++++++++++++++++++++ Métodos privados - End ++++++++++++++++++++++++++++++++++++++++++++


    //************************
    // Atributos de Base_Iterator.

    // Dirección de avance.
    Iterator_Direction direction_;

    // Nodo falso que indica que el iterador está mas allá del final.
    Base_Node<T> dummy_after_end_;

    // Nodo falso que indica que el iterador está antes del principio.
    Base_Node<T> dummy_before_begin_;

    // Nodo actual.
    Base_Node<T>* current_;

    //************************

};

/* ========================= Base_Iterator - End ========================== */


/* ========================= Iterator_Printer - Begin ===================== */

template <typename T>
class Iterator_Printer
{

private:

    // Flujo de salida.
    std::ostream& oss;

    // Separador.
    std::string sep_;

    // Última clave impresa.
    const T* old;

public:

    // Constructor.
    Iterator_Printer(std::ostream& o, const std::string& sep = ","):oss(o), sep_(sep), old(NULL)
    {};

    // Operador de ejecución.
    void operator() (const T& key)
    {
        oss << (old?sep_:"") << key;

        old = &key;
    }
};

/* ========================= Iterator_Printer - End ======================= */

// ++++++++++++++++++++++++ Constructores\Destructores [SetImplementation] - Begin ++++++++++++++++++++++++++

// Constructor.
template <typename T>
SetImplementation<T>::SetImplementation()
{
};

//Destructor.
template <typename T>
SetImplementation<T>::~SetImplementation()
{
};

// ++++++++++++++++++++++++ Constructores\Destructores [SetImplementation] - End ++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [SetImplementation] - Begin ++++++++++++++++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
SetImplementation<T>& SetImplementation<T>::operator=(const SetImplementation<T>& container)
{
    // Verifico la autoasignación.
    if (&container == this)
        return *this;

    // Vacío el contenedor.
    wipe();

    // Caso especial de copia de dos contenedores derivados distintos,
    // esto se da si se copian haciendo una asignación desreferenciando dos punteros
    // a esta clase base.
    // Esto simplifica la implementación en el "Handle".
    // Esto nunca será ejecutado al ser llamado por los operadores
    // de copia de las clases derivadas, en ese caso ambos objetos
    // pertenecen a la misma clase derivada, y solo se obtiene el comportamiento
    // básico (copia de la cantidad de elementos).
    // La copia es respecto solo a elementos contenidos, en cambio cuándo
    // se trata de objetos de la misma clase la copia es también
    // a nivel structura.
    if (typeid(container) != typeid(*this))
    {
        for (iterator it = container.begin(); it != container.end(); it++)
        {
            // Debo aceptar todos los elemntos por tratarse
            // de una copia, de estarse implementando un conjunto
            // naturalmente no habrá elemntos repetidos.
            add(*it, true);
        }
    }

    return *this;
}

// Operador de salida.
template <typename T>
std::ostream& SetImplementation<T>::operator<<(std::ostream & oss)
{
	print(oss);

	return oss;
}

// ++++++++++++++++++++++++ Operadores [SetImplementation] - End ++++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Constructores\Destructores [Base_Node] - Begin +++++++++++++++++++++++++++++

// Constructor.
template <typename T>
Base_Node<T>::Base_Node(const Base_Container<T>& container, const T& key): key_(key), container_(&container)
{
}

// Constructor.
template <typename T>
Base_Node<T>::Base_Node(const Base_Container<T>& container): container_(&container)
{
}

// Constructor copia.
template <typename T>
Base_Node<T>::Base_Node(const Base_Node& node): key_(node.key_), container_(node.container_)
{
}

// Destructor.
template <typename T>
Base_Node<T>::~Base_Node()
{
}

// ++++++++++++++++++++++++ Constructores\Destructores [Base_Node] - End +++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos públicos [Base_Node] - Begin +++++++++++++++++++++++++++++++++++++++

// Devuelve una referencia al contenedor.
template <typename T>
const Base_Container<T>& Base_Node<T>::container()
{
    return *container_;
}

// ++++++++++++++++++++++++ Métodos públicos [Base_Node] - End +++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Base_Node] - Begin +++++++++++++++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
Base_Node<T>& Base_Node<T>::operator=(const Base_Node<T>& node)
{
    // Verifico la autoasignación.
    if (&node == this)
        return *this;

    container_ = node.container_;

    return *this;
}

// ++++++++++++++++++++++++ Operadores [Base_Node] - End +++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Constructores\Destructores [Base_Container] - Begin ++++++++++++++++++++++++

// Constructor.
template <typename T>
Base_Container<T>::Base_Container(): node_count_(0)
{
}

// Constructor copia.
template <typename T>
Base_Container<T>::Base_Container(const Base_Container<T>& container): node_count_(container.node_count_)
{
}

// Destructor.
template <typename T>
Base_Container<T>::~Base_Container()
{
}

// ++++++++++++++++++++++++ Constructores\Destructores [Base_Container] - End ++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos públicos [Base_Container] - Begin +++++++++++++++++++++++++++++++++++

// Devuelve el iterador al primer elemento.
template <typename T>
typename Base_Container<T>::iterator Base_Container<T>::begin() const
{
    return iterator(*this, SN_BEGIN);
}

// Devuelve el iterador al siguiente al último elemento.
template <typename T>
typename Base_Container<T>::iterator Base_Container<T>::end() const
{
    return iterator(*this, SN_END);
}

// Devuelve el iterador al anterior al primer elemento.
template <typename T>
typename Base_Container<T>::iterator Base_Container<T>::rend() const
{
    iterator it(*this, SN_R_BEGIN);

    return it;
}

// Devuelve el iterador al último elemento.
template <typename T>
typename Base_Container<T>::iterator Base_Container<T>::rbegin() const
{
    iterator it(*this, SN_R_END);

    return it;
}

// Agrega un elemento al contenedor.
template <typename T>
bool Base_Container<T>::add(const T& key, bool accept_repeated)
{
	return (add_hidden(key, accept_repeated) != NULL);
}

// Agrega un elemento al contenedor y devuelve un iterador al mismo, o al elemento existente en caso de existir previamente.
template <typename T>
typename Base_Container<T>::iterator Base_Container<T>::add_or_get(const T& key)
{
    Base_Node<T>* node = find_node(key);

    if (node == NULL)
        node = add_hidden(key, false);

    return iterator(*this, node);
}

// Elimina un elemento del contenedor (si se encuentra).
template <typename T>
bool Base_Container<T>::remove(const T& key)
{
	bool deleted = false;

	// Si el contenedor solo necesita la clave para borrar el nodo.
	if (!(delete_node_by_key(key, deleted)))
	{
		// Encuentro el elemento a eliminar.
		Base_Node<T>* node = find_node(key);

		if (node != NULL)
		{
			// Borro el elemento.
			delete_node(node);

			deleted = true;
		}
	}

	// Si se borro un elemnto, decremento el contador.
	if (deleted)
		node_count_--;

	return deleted;
}

// Determina si un elemento se encuentra en el contenedor.
template <typename T>
bool Base_Container<T>::includes(const T& key) const
{
    return (find_node(key) != NULL);
}

// Vacía el contenedor.
template <typename T>
void Base_Container<T>::wipe()
{
    // Booro todos los elementos.
    delete_nodes();

    // Reinicializo la cantidad de elementos.
    node_count_ = 0;
}

// Determina si el contenedor esta vacío.
template <typename T>
bool Base_Container<T>::is_empty() const
{
    return (node_count_ == 0);
}

// Devuelve la cantidad de elementos en el contenedor.
template <typename T>
size_t Base_Container<T>::size() const
{
    return node_count_;
}

// Imprime los elementos contenidos.
template <typename T>
void Base_Container<T>::print(std::ostream& oss) const
{
    oss << '{';

    for_each(begin(), end(), Iterator_Printer<T>(oss));

    oss << '}';
}

// Devuelve un string que identifica a la clase del contenedor.
// Dado que es dependiente de la implementación, puede que
// no se vea algo "lindo", de hecho g++ devuelve un nombre "mangled".
template <typename T>
std::string Base_Container<T>::class_ID() const
{
    std::string class_name = typeid(*this).name();

	if (class_name.find(STR_CLASS_NAME) != std::string::npos)
        class_name.erase(0, std::string(STR_CLASS_NAME).length());

    return class_name;
}

// ++++++++++++++++++++++++ Métodos públicos [Base_Container] - End +++++++++++++++++++++++++++++++++++++++++

// ++++++++++++++++++++++++ Métodos protegidos [Base_Container] - Begin +++++++++++++++++++++++++++++++++++++++

// Agrega un elemento al contenedor (Devuelve puntero al nodo).
template <typename T>
Base_Node<T>* Base_Container<T>::add_hidden(const T& key, bool accept_repeated)
{
	Base_Node<T>* node;

    if ((node = add_node(key, accept_repeated)) != NULL)
    {
        // Incremento la cantidad de elementos.
        node_count_++;        
    }

	return node;
}

// ++++++++++++++++++++++++ Métodos protegidos [Base_Container] - End +++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Base_Container] - Begin +++++++++++++++++++++++++++++++++++++++++++++

// Operador de asignación.
template <typename T>
Base_Container<T>& Base_Container<T>::operator=(const Base_Container<T>& container)
{
    // Verifico la autoasignación.
    if (&container == this)
        return *this;

    // Llamo al operador de asignación de la clase base.
    SetImplementation<T>::operator=(container);

    // Copio la cantidad de elementos.
    node_count_ = container.node_count_;

    return *this;
}

// ++++++++++++++++++++++++ Operadores [Base_Container] - End +++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Constructores\Destructores [Base_Iterator] - Begin ++++++++++++++++++++++++++++++

// Constructor.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>::Base_Iterator(const Base_Container<T>& container):
    container_(&container), direction_(ID_FORWARD), dummy_after_end_(container), dummy_before_begin_(container)
{
    if (!container.is_empty())
        set_node(container.first(itt));
    else
        goto_end();
};

// Constructor copia.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>::Base_Iterator(const Base_Iterator& it):
    container_(it.container_), direction_(it.direction_), dummy_after_end_(*container_), dummy_before_begin_(*container_)
{
    *this = it;
}

// Constructor que crea e inicializa el elemento en algún extremo o más allá.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>::Base_Iterator(const Base_Container<T>& container, Special_Node sn):
    container_(&container), direction_(ID_FORWARD), dummy_after_end_(container), dummy_before_begin_(container)
{
    switch (sn)
    {
    case SN_BEGIN:
        goto_begin();
        break;
    case SN_R_BEGIN:
        goto_rend();
        set_direction(ID_BACKWARD);
        break;
    case SN_END:
        goto_end();
        break;
    case SN_R_END:
        goto_rbegin();
        set_direction(ID_BACKWARD);
        break;
    default:
        goto_begin();
    }
}

// Destructor.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>::~Base_Iterator()
{
};


// Constructor protegido que crea el iterador e inicializa el elemento a uno en particular.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>::Base_Iterator(const Base_Container<T>& container, Base_Node<T>* node):
    container_(&container), direction_(ID_FORWARD), dummy_after_end_(container), dummy_before_begin_(container)
{
    set_node(node);
}

// ++++++++++++++++++++++++ Constructores\Destructores [Base_Iterator] - End ++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos públicos [Base_Iterator] - Begin ++++++++++++++++++++++++++++++++++++++++

// Devuelve la dirección de avance del iterador bidireccional
// (solo cambia el sentido de los operadores de incremento y decremento).
template <typename T, Iterator_Type itt>
Iterator_Direction Base_Iterator<T, itt>::get_direction()
{
    return direction_;
}

// Setea la dirección de avance del iterador bidireccional
// (solo cambia el sentido de los operadores de incremento y decremento).
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::set_direction(Iterator_Direction d)
{
    direction_ = d;
}

// Fuerza el iterador al primer elemento.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::goto_begin()
{
    if (!container_->is_empty())
        set_node(SN_BEGIN);
    else
        set_node(SN_END);
}

// Fuerza el iterador al elemento siguiente al último.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::goto_end()
{
    set_node(SN_END);
}

// Fuerza el iterador al elemento anterior al primero.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::goto_rend()
{
    set_node(SN_R_BEGIN);
}

// Fuerza el iterador al último elemento.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::goto_rbegin()
{
    if (!container_->is_empty())
        set_node(SN_R_END);
    else
        set_node(SN_R_BEGIN);
}

// ++++++++++++++++++++++++ Métodos públicos [Base_Iterator] - Begin ++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Operadores [Base_Iterator] - Begin ++++++++++++++++++++++++++++++++++++++++++++++

// Operador de desreferenciación.
template <typename T, Iterator_Type itt>
const T& Base_Iterator<T, itt>::operator*()
{
    if ((current_ == NULL) || (current_ == &dummy_before_begin_) || (current_ == &dummy_after_end_))
        FATAL_ERROR(BAD_ITERATOR);

    return current_->key_;
}

// Operador de comparación por igualdad.
template <typename T, Iterator_Type itt>
bool Base_Iterator<T, itt>::operator==(const Base_Iterator<T, itt>& it) const
{
    // Si apuntan al mismo elemento o si ambos apuntan antes del principio
    // o después del final, siendo ambos iteradores del mismo contenedor.
    return ((container_ == it.container_) &&
            ((current_ == it.current_) ||
             ((current_ == &dummy_before_begin_) && (it.current_ == &(it.dummy_before_begin_))) ||
             ((current_ == &dummy_after_end_) && (it.current_ == &(it.dummy_after_end_)))));
}

// Operador de comparación por desigualdad.
template <typename T, Iterator_Type itt>
bool Base_Iterator<T, itt>::operator!=(const Base_Iterator<T, itt>& it) const
{
    return (!(*this == it));
}

// Operador de asignación.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>& Base_Iterator<T, itt>::operator=(const Base_Iterator<T, itt>& it)
{
    // Verifico la autoasignación.
    if (&it == this)
        return *this;

    // Copio el puntero al contenedor.
    container_ = it.container_;

    // Copio la dirección de avance.
    direction_ = it.direction_;

    // Copio el puntero al elemento apuntado.
    if (it.current_ == &(it.dummy_before_begin_))
        current_ = &dummy_before_begin_;
    else if	(it.current_ == &(it.dummy_after_end_))
        current_ = &dummy_after_end_;
    else
        current_ = it.current_;

    return *this;
}

// Operador de pre-incremento.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>& Base_Iterator<T, itt>::operator++()
{
    if (direction_ == ID_FORWARD)
        next();
    else
        previous();

    return *this;
}

// Operador de pre-decremento.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt>& Base_Iterator<T, itt>::operator--()
{
    if (direction_ == ID_FORWARD)
        previous();
    else
        next();

    return *this;
}

// Operador de post-incremento.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt> Base_Iterator<T, itt>::operator++(int)
{
    Base_Iterator<T, itt> temp(*this);

    operator++();

    return temp;
}

// Operador de post-decremento.
template <typename T, Iterator_Type itt>
Base_Iterator<T, itt> Base_Iterator<T, itt>::operator--(int)
{
    Base_Iterator<T, itt> temp(*this);

    operator--();

    return temp;
}

// ++++++++++++++++++++++++ Operadores [Base_Iterator] - End ++++++++++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos protegidos [Base_Iterator] - Begin ++++++++++++++++++++++++++++++++++++++

// Incrementa el iterador.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::next()
{
    if (current_ == &dummy_after_end_)
        FATAL_ERROR(BAD_ITERATOR);

    if (current_ == &dummy_before_begin_)
    {
        if (!container_->is_empty())
            set_node(SN_BEGIN);
        else
            set_node(SN_END);

        return;
    }

    Base_Node<T>* n = container_->next(current_, itt);

    // Si llegué al final.
    if (n == NULL)
        current_ = &dummy_after_end_;
    else
        current_ = n;
}

// Decrementa el iterador.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::previous()
{
    if (current_ == &dummy_before_begin_)
        FATAL_ERROR(BAD_ITERATOR);

    if (current_ == &dummy_after_end_)
    {
        if (!container_->is_empty())
            set_node(SN_R_END);
        else
            set_node(SN_R_BEGIN);

        return;
    }

    Base_Node<T>* n = container_->previous(current_, itt);

    // Si llegué al principio.
    if (n == NULL)
        current_ = &dummy_before_begin_;
    else
        current_ = n;
}

// ++++++++++++++++++++++++ Métodos protegidos [Base_Iterator] - End ++++++++++++++++++++++++++++++++++++++++


// ++++++++++++++++++++++++ Métodos privados [Base_Iterator] - Begin ++++++++++++++++++++++++++++++++++++++++

// Fuerza el iterador a un elemento determinado.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::set_node(Special_Node sn)
{
    switch (sn)
    {
    case SN_BEGIN:
        current_ = container_->first(itt);
        break;
    case SN_R_BEGIN:
        current_ = &dummy_before_begin_;
        break;
    case SN_END:
        current_ = &dummy_after_end_;
        break;
    case SN_R_END:
        current_ = container_->last(itt);
        break;
    default:
        current_ = container_->first(itt);
    }
}

// Fuerza el iterador a un elemento determinado.
template <typename T, Iterator_Type itt>
void Base_Iterator<T, itt>::set_node(Base_Node<T>* node)
{
    if ((node == NULL) ||(&(node->container()) != container_))
        FATAL_ERROR(BAD_ITERATOR);

    current_ = node;
}

// ++++++++++++++++++++++++ Métodos privados [Base_Iterator] - End ++++++++++++++++++++++++++++++++++++++++++

#endif
